/*
 * @lc app=leetcode.cn id=148 lang=javascript
 *
 * [148] 排序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */

/**
 * 快速排序
 * 
 * head作为中间值
 * 小值放在head前，大值放head后 
 */ 
function quick_sort(head, end){
  if(head === end || head.next === end){ return head};
  let lHead = head, rHead = head, p = head.next;

  while(p!= end){
    // 保存下一个节点
    let next = p.next;
    
    // 小值放在head前面
    if(p.val < head.val){
      p.next = lHead;
      lHead = p;
    // 大值放在head后面
    } else {
      rHead.next = p;
      rHead = p;
    }
    p = next;
  }
  
  rHead.next = end;
  let node = quick_sort(lHead, head);
  head.next = quick_sort(head.next, end);
  return node;
}
var sortList = function(head) {
  return quick_sort(head, null);
}

/**
 * 归并排序
 * 
 * 利用快慢指针查找中间节点
 * 处理左边，处理右边，再合并
 */
// var splitList = function(head, tail){
//   if(head === tail) return head;
//   // 头结点等于尾节点，头结点next置为null,断开链表
//   if(head.next === tail){
//     head.next = null;
//     return head;
//   }

//   let slow = head, fast = head;
//   while(fast !== tail){
//     slow = slow.next;
//     fast = fast.next;
//     if(fast !== tail) fast = fast.next;
//   }
//   const mid = slow;
//   var leftH = splitList(head, mid);
//   var rightH = splitList(mid, tail)
//   return merge(leftH, rightH);
// }
// var merge = function(head1, head2){
//   var head = new ListNode(null);
//   let p1 = head1, p2 = head2, cur = head;
//   while(p1 && p2){
//     if(p1.val < p2.val){
//       cur.next = p1;
//       p1 = p1.next;
//     } else {
//       cur.next = p2;
//       p2 = p2.next;
//     }
//     cur = cur.next;
//   }
//   if(p1) {
//     cur.next = p1;
//   } else if(p2){
//     cur.next = p2;
//   }

//   return head.next;
// }
// var sortList = function(head) {
//   return splitList(head, null);
// }

// @lc code=end

